package levelorder;

import entity.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class LevelOrderTraversalII {
    /*
    * 二叉树的层序遍历II
    * 给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。
    * （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
    *
    * 树中节点数目在范围 [0, 2000] 内
    * -1000 <= Node.val <= 1000
    *
    * */
    public static void main(String[] args){
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        LevelOrderTraversalII o = new LevelOrderTraversalII();
        o.mySolution(root);
    }

    // 将正常层序遍历的结果反转就好了
    public List<ArrayList<Integer>> mySolution(TreeNode root){
        // 利用LinkedList头插法，直接反序添加就好了
        LinkedList<ArrayList<Integer>> res = new LinkedList<>();
        if(root == null)
            return res;
        LinkedList<TreeNode> deque = new LinkedList<>();
        deque.add(root);
        while (!deque.isEmpty()){
            ArrayList<Integer> r = new ArrayList<>();
            int len = deque.size();
            while (len > 0){
                root = deque.pop();
                r.add(root.val);
                if(root.left != null) deque.add(root.left);
                if(root.right != null) deque.add(root.right);
                len--;
            }
            res.addFirst(r); // 写入结果
        }
        return res;
    }
}

